#pragma once

#include <initializer_list>
#include "log_functor.hpp"
#include "tree_node.hpp"

namespace zuck
{
	template<bool multi, typename value_type>
	__tree_node<multi, value_type> NIL;
	template<bool multi, typename value_type>
	__tree_node<multi, value_type> NIR;
	template<bool multi, typename value_type>
	__tree_node<multi, value_type>* const nil{ zuck::address_of(NIL<multi, value_type>) };
	template<bool multi, typename value_type>
	__tree_node<multi, value_type>* const nir{ zuck::address_of(NIR<multi, value_type>) };

	template<bool multi, typename T = void>
	class __ptr_move;
	template<typename T>
	class __ptr_move<false, T> {
	public:
		using value_type = T;
	private:
		using _Node_ptr	= __tree_node<false, T>*;
	public:
		ZNODISCARD static _Node_ptr _m_prev(_Node_ptr ptr)
		{
			if (ptr->__l != nil<false, T> &&
				ptr->__l != null)
			{
				ptr = ptr->__l;
				for (; ptr->__r != nil<false, T> && ptr->__r->__r != null;) {
					ptr = ptr->__r;
				}
				return ptr;
			}
			for (; ptr->_m_p != nil<false, T> && // trans node can not visit nir and null
				   ptr->_m_p != nir<false, T> &&
				   ptr && ptr != ptr->_m_p->__r;)
			{
				ptr = ptr->_m_p;
			}
			return ptr->_m_p;
		}

		ZNODISCARD static _Node_ptr __next(_Node_ptr ptr)
		{
			if (ptr->__r != nil<false, T> && ptr->__r) {
				ptr = ptr->__r;
				for (; ptr->__l != nil<false, T> && ptr->__l->__l;) {
					ptr = ptr->__l;
				}
				return ptr;
			}
			for (; ptr->_m_p != nil<false, T> && // same as the previous
				   ptr->_m_p != nir<false, T> &&
				   ptr &&  ptr != ptr->_m_p->__l;)
			{
				ptr = ptr->_m_p;
			}
			return ptr->_m_p;
		}
	};

	// no implement
	template<typename T>
	class __ptr_move<true, T> {};

	template<bool multi, typename _Tree>
	class __RBTreeConstIterator {
	public:
		using value_type		= typename _Tree::value_type;
		using pointer	        = value_type const*;
		using const_pointer		= value_type const*;
		using reference			= value_type const&;
		using difference_type   = typename _Tree::difference_type;
		using iterator_category = bidirectional_iterator_tag;
	private:
		using _Node_ptr = __tree_node<multi, value_type>*;
		using _Self = __RBTreeConstIterator<multi, _Tree>;
	private:
		_Node_ptr _m_iter;
		_Node_ptr _m_prev;
	public:
		explicit __RBTreeConstIterator(_Node_ptr iter, _Node_ptr prev)
			: _m_iter(iter), _m_prev(prev) {}

		__RBTreeConstIterator(const __RBTreeConstIterator& other)
			: _m_iter(other._m_iter), _m_prev(other._m_prev) {}

		__RBTreeConstIterator(__RBTreeConstIterator&& other)noexcept
			: _m_iter(other._m_iter), _m_prev(other._m_prev)
		{
			other._m_iter = nil<multi, value_type>;
			other._m_prev = nil<multi, value_type>;
		}

		inline virtual ~__RBTreeConstIterator()
		{
			_m_iter = nil<multi, value_type>;
			_m_prev = nil<multi, value_type>;
		}

		ZNODISCARD inline _Node_ptr get_unwrapped()const
		{ return _m_iter->__d; }

		__RBTreeConstIterator& operator=(const _Self& _other)
		{
			_m_iter = _other._m_iter;
			_m_prev = _other._m_prev;
			return *this;
		}

		__RBTreeConstIterator& operator=(_Self&& _other)noexcept
		{
			_m_iter = _other._m_iter;
			_m_prev = _other._m_prev;
			_other._m_iter = nil<multi, value_type>;
			_other._m_prev = nil<multi, value_type>;
			return *this;
		}

		ZNODISCARD inline pointer operator->()const noexcept
		{
			if constexpr (debug_) {
				if (_m_iter == nil<multi, value_type> ||
					_m_iter == nir<multi, value_type> || !_m_iter)
				{
					debug_log::derror(zuck::SEG_WrongIter, 
						"Invalid iterator !");
				}
			}
			return _m_iter->__d;
		}

		ZNODISCARD inline reference operator*()const noexcept
		{
			if constexpr (debug_) {
				if (_m_iter == nil<multi, value_type> ||
					_m_iter == nir<multi, value_type> || !_m_iter)
				{
					debug_log::derror(zuck::SEG_WrongIter,
						"can not referenced end rbtree iterartor !");
				}
			}
			return *(_m_iter->__d);
		}

		__RBTreeConstIterator& operator++()noexcept
		{
			_m_iter = __ptr_move<multi, value_type>::__next(_m_iter);
			return *this;
		}

		ZNODISCARD __RBTreeConstIterator operator++(int)noexcept
		{
			auto _Tmp = *this;
			++(*this);
			return _Tmp;
		}

		inline __RBTreeConstIterator& operator--()noexcept
		{
			_m_iter == nir<multi, value_type> ?
				_m_iter = _m_prev :
				_m_iter = __ptr_move<multi, value_type>::_m_prev(_m_iter);
			return *this;
		}

		ZNODISCARD inline __RBTreeConstIterator operator--(int)noexcept
		{
			auto _Tmp = *this;
			--(*this);
			return _Tmp;
		}

		ZNODISCARD inline bool operator==(_Node_ptr ptr)const noexcept
		{ return static_cast<bool>(_m_iter == ptr); }

		ZNODISCARD inline bool operator!=(_Node_ptr ptr)const noexcept
		{ return static_cast<bool>(_m_iter != ptr); }

		ZNODISCARD inline bool operator==(const _Self& _other)const noexcept
		{ return static_cast<bool>(_m_iter == _other._m_iter); }

		ZNODISCARD inline bool operator!=(const _Self& _other)const noexcept
		{ return static_cast<bool>(_m_iter != _other._m_iter); }
	};


	template<bool multi, typename _Tree>
	class __RBTreeIterator : public __RBTreeConstIterator<multi, _Tree>
	{
	private:
		using _Self = __RBTreeIterator<multi, _Tree>;
		using _Base = __RBTreeConstIterator<multi, _Tree>;
	public:
		using value_type		= typename _Base::value_type;
		using pointer			= value_type*;
		using const_pointer		= value_type const*;
		using reference			= value_type&;
		using difference_type	= typename _Tree::difference_type;
		using iterator_category = typename _Base::iterator_category;
	private:
		using _Node_ptr = __tree_node<multi, value_type>*;
	public:
		explicit __RBTreeIterator(_Node_ptr iter, _Node_ptr prev)
			: _Base(iter, prev) {}

		__RBTreeIterator(const _Self& other)
			: _Base(other) {}

		__RBTreeIterator(_Self&& other)noexcept
			: _Base(zuck::move(other)) {}

		inline _Self& operator=(_Self const& other)
		{
			_Base::operator=(other);
			return *this;
		}

		inline _Self& operator=(_Self&& other)noexcept
		{
			_Base::operator=(zuck::move(other));
			return *this;
		}

		ZNODISCARD inline reference operator*()noexcept
		{ return const_cast<reference>(_Base::operator*()); }

		ZNODISCARD inline pointer operator->()noexcept
		{ return const_cast<pointer>(_Base::operator->()); }

		inline _Self& operator++()noexcept
		{
			_Base::operator++();
			return *this;
		}

		ZNODISCARD inline _Self operator++(int)noexcept
		{
			auto _Tmp = *this;
			_Base::operator++();
			return _Tmp;
		}

		inline _Self& operator--()noexcept
		{
			_Base::operator--();
			return *this;
		}

		ZNODISCARD inline _Self operator--(int)noexcept
		{
			auto _Tmp = *this;
			_Base::operator--();
			return _Tmp;
		}
	};


	template<bool multi, typename _Tree>
	class __RBTreeConstReverseIterator {
	public:
		using value_type        = typename _Tree::value_type;
		using pointer	        = value_type const*;
		using reference			= value_type const&;
		using difference_type	= typename _Tree::difference_type;
		using iterator_category = bidirectional_iterator_tag;
	private:
		using _Node_ptr = __tree_node<multi, value_type>*;
		using _Node_t   = __tree_node<multi, value_type>;
		using _Self		= __RBTreeConstReverseIterator<multi, _Tree>;
	private:
		_Node_ptr _m_iter;
		_Node_ptr _m_prev;
	public:
		__RBTreeConstReverseIterator(_Node_ptr iter, _Node_ptr prev)
			: _m_iter(iter), _m_prev(prev) {}

		__RBTreeConstReverseIterator(const _Self& _other)
			:_m_iter(_other._m_iter), _m_prev(_other._m_prev)
		{}

		__RBTreeConstReverseIterator(_Self&& _other)noexcept
			:_m_iter(_other._m_iter), _m_prev(_other._m_prev)
		{
			_other._m_iter = nil<multi, value_type>;
			_other._m_prev = nil<multi, value_type>;
		}

		inline virtual ~__RBTreeConstReverseIterator()
		{
			_m_iter = null;
			_m_prev = null;
		}

		ZNODISCARD inline _Node_ptr get_unwrapped()const
		{ return _m_iter; }

		inline _Self& operator=(_Self const& other)
		{
			_m_iter = other._m_iter;
			_m_prev = other._m_prev;
			return *this;
		}
		
		inline _Self& operator=(_Self&& other)noexcept
		{
			_m_iter = other._m_iter;
			_m_prev = other._m_prev;
			other._m_iter = nil<multi, value_type>;
			other._m_prev = nil<multi, value_type>;
			return *this;
		}

		ZNODISCARD inline pointer operator->()const noexcept
		{
			if constexpr (debug_) {
				if (_m_iter == nil<multi, value_type> ||
					_m_iter == nir<multi, value_type> || !_m_iter)
				{
					debug_log::derror(zuck::SEG_WrongIter, 
						"can not referenced end rbtree iterartor !");
				}
			}
			return _m_iter->__d;
		}

		ZNODISCARD inline reference operator*()const noexcept
		{
			if constexpr (debug_) {
				if (_m_iter == nil<multi, value_type> ||
					_m_iter == nir<multi, value_type> || !_m_iter)
				{
					debug_log::derror(zuck::SEG_WrongIter, 
						"can not referenced end rbtree iterartor !");
				}
			}
			return *(_m_iter->__d);
		}

		inline __RBTreeConstReverseIterator& operator++()noexcept
		{
			_m_iter = __ptr_move<multi, value_type>::_m_prev(_m_iter);
			return *this;
		}

		ZNODISCARD inline __RBTreeConstReverseIterator operator++(int)noexcept
		{
			auto _Tmp = *this;
			++(*this);
			return _Tmp;
		}

		inline __RBTreeConstReverseIterator& operator--()noexcept
		{
			_m_iter == nil<multi, value_type> ?
				_m_iter = _m_prev :
				_m_iter = __ptr_move<multi, value_type>::__next(_m_iter);
			return *this;
		}

		ZNODISCARD inline __RBTreeConstReverseIterator operator--(int)noexcept
		{
			auto _Tmp = *this;
			--(*this);
			return _Tmp;
		}

		ZNODISCARD inline bool operator==(const _Self& other)const noexcept
		{ return static_cast<bool>(_m_iter == other._m_iter); }

		ZNODISCARD inline bool operator!=(const _Self& other)const noexcept
		{ return static_cast<bool>(_m_iter != other._m_iter); }
	};


	template<bool multi, typename _Tree>
	class __RBTreeReverseIterator : public __RBTreeConstReverseIterator<multi, _Tree>
	{
	private:
		using _Self = __RBTreeReverseIterator<multi, _Tree>;
		using _Base = __RBTreeConstReverseIterator<multi, _Tree>;
	public:
		using value_type = typename _Tree::value_type;
		using pointer    = value_type*;
		using reference  = value_type&;
		using difference_type	= typename _Tree::difference_type;
		using iterator_category = typename _Base::iterator_category;
	private:
		using _Node_ptr = __tree_node<multi, value_type>*;
		using _Node_t   = __tree_node<multi, value_type>;
	public:
		explicit __RBTreeReverseIterator(_Node_ptr iter, _Node_ptr prev)
			: _Base(iter, prev) {}

		__RBTreeReverseIterator(const _Self& other) : _Base(other) {}

		__RBTreeReverseIterator(_Self&& other) : _Base(zuck::move(other)) {}

		inline _Self& operator=(const _Self& other)
		{
			_Base::operator=(other);
			return *this;
		}

		inline _Self& operator=(_Self&& other)noexcept
		{
			_Base::operator=(zuck::move(other));
			return *this;
		}

		ZNODISCARD inline pointer operator->()noexcept
		{ return const_cast<pointer>(_Base::operator->()); }

		ZNODISCARD inline reference operator*()noexcept
		{ return const_cast<reference>(_Base::operator*()); }

		inline _Self& operator++()noexcept
		{
			_Base::operator++();
			return *this;
		}

		ZNODISCARD inline _Self operator++(int)noexcept
		{
			auto _Tmp = *this;
			_Base::operator++();
			return _Tmp;
		}

		inline _Self& operator--()noexcept
		{
			_Base::operator--();
			return *this;
		}

		ZNODISCARD inline _Self operator--(int)noexcept
		{
			auto _Tmp;
			_Base::operator--();
			return _Tmp;
		}
	};


	template<typename _Traits>
	class _rbtree {
	protected:
		static inline bool constexpr multi = _Traits::_Multi;
		bool __exist;
	private:
		using _Alty_tts = ::zuck::allocator_traits<typename _Traits::allocator_type>;
	public:
		using key			   = typename _Traits::key_type;
		using value_type	   = typename _Traits::value_type;
		using pointer          = value_type*;
		using reference		   = value_type&;
		using const_reference  = value_type const&;
		using rvalue_reference = value_type&&;
		using size_type		   = ::zuck::size_t;
		using difference_type  = ::zuck::ptrdiff_t;
		using key_compare	   = typename _Traits::key_compare;
		using equal			   = typename _Traits::equal;
		using allocator_type   = typename _Traits::allocator_type;
	private:
		using _Node_t	  = __tree_node<multi, value_type>;
		using _Node_ptr	  = __tree_node<multi, value_type>*;
		using _Self		  = _rbtree<_Traits>;
		using Alloc	      = typename _Traits::allocator_type;
		using _Node_Alloc = __tree_node<multi, value_type>;
	public:
		using iterator				 = __RBTreeIterator<multi, _rbtree<_Traits>>;
		using const_iterator		 = __RBTreeConstIterator<multi, _rbtree<_Traits>>;
		using reverse_iterator		 = __RBTreeReverseIterator<multi, _rbtree<_Traits>>;
		using const_reverse_iterator = __RBTreeConstReverseIterator<multi, _rbtree<_Traits>>;
	protected:
		_Node_ptr   _m_root;
		size_type   _m_cnt;
		key_compare	__cmp;
		equal       __equal;
		Alloc      alloc;
	public:
		explicit _rbtree()noexcept 
			: _m_root(nil<multi, value_type>)
			, _m_cnt(0)
			, __equal(equal{})
			, __cmp(key_compare{})
			, alloc(Alloc{})
		{}

		_rbtree(std::initializer_list<value_type> data)
			: _m_root(nil<multi, value_type>)
			, _m_cnt(0)
			, __cmp(key_compare{})
			, __equal(equal{})
			, alloc(allocator_type{})
		{
			__construct_range(data.begin(), data.end());
		}

		_rbtree(std::initializer_list<value_type> data, Alloc al)
			: _m_root(nil<multi, value_type>)
			, _m_cnt(0)
			, __cmp(key_compare{})
			, __equal(equal{})
			, alloc(al)
		{
			__construct_range(data.begin(), data.end());
		}

		template<typename InputIterator,
			zuck::enable_if_t<zuck::is_input_iterator_v<InputIterator>, int> = 0>
		explicit _rbtree(InputIterator Begin, InputIterator End)
			: _m_root(nil<multi, value_type>), _m_cnt(0)
			, __cmp(key_compare{}), __equal(equal{})
			, alloc(allocator_type{})
		{
			__construct_range(Begin, End);
		}

		template<typename InputIterator,
			zuck::enable_if_t<zuck::is_input_iterator_v<InputIterator>, int> = 0>
		explicit _rbtree(InputIterator Begin, InputIterator End, Alloc al)
			: _m_root(nil<multi, value_type>), _m_cnt(0)
			, __cmp(key_compare{}), __equal(equal{})
			, alloc(al)
		{
			__construct_range(Begin, End);
		}

		inline _rbtree(_rbtree const& other)
			: _m_root(nil<multi, value_type>), _m_cnt(0)
			, __cmp(other.__cmp), __equal(other.__equal)
			, alloc(other.alloc)
		{
			__copy_aux(other.begin(), other.end());
		}

		explicit _rbtree(const _rbtree& other, key_compare _pr)
			: _m_root(nil<multi, value_type>)
			, _m_cnt(0)
			, __cmp(_pr)
			, __equal(equal{})
			, alloc(allocator_type{})
		{
			__copy_aux(other.begin(), other.end());
		}

		inline _rbtree(_rbtree&& other)noexcept
			: _m_root(other._m_root), _m_cnt(other._m_cnt)
			, __cmp(other.__cmp), __equal(other.__equal)
			, alloc(other.alloc)
		{
			other._m_root = nil<multi, value_type>;
			other._m_cnt  = 0;
		}

		inline virtual ~_rbtree()
		{ __destroy_tree(_m_root); }

		inline void clear()
		{ __destroy_tree(_m_root); }

		ZNODISCARD size_type count(const key& _K)
		{
			if constexpr (multi) {

			}
			else {
				__find_node(_K);
			}
		}

		ZNODISCARD size_type count(key&& _K)
		{
			if constexpr (multi) {

			}
			else {
				__find_node(_K);
			}
		}

		ZNODISCARD iterator find(const key& _K)
		{ return __find_node(_K); }

		ZNODISCARD iterator find(key&& _K)
		{ return __find_node(zuck::move(_K)); }

		void insert(const value_type& val)
		{ __insert_aux(val); }

		void insert(value_type&& val)
		{ __insert_aux(val); }

		template<typename InputIterator,
			zuck::enable_if_t<zuck::is_input_iterator_v<InputIterator>, int> = 0>
		void insert(InputIterator Begin, InputIterator End)
		{
			for (; Begin != End;) {
				__insert_aux(*Begin);
			}
		}

		ZNODISCARD inline bool empty()const noexcept
		{ return static_cast<bool>(!_m_cnt); }

		ZNODISCARD inline size_type size()const noexcept
		{ return _m_cnt; }

		ZNODISCARD inline size_type max_size()const noexcept
		{ return _Alty_tts::max_size(); }

		inline void swap(_rbtree& other)noexcept
		{
			auto _Tmp = zuck::move(other);
			other	  = zuck::move(*this);
			*this	  = zuck::move(_Tmp);
		}

		ZNODISCARD inline iterator begin()noexcept
		{ return iterator(_Min()); }

		ZNODISCARD inline const_iterator begin()const noexcept
		{ return const_iterator(_Min()); }

		ZNODISCARD inline const_iterator cbegin()const noexcept
		{ return const_iterator(_Min()); }

		ZNODISCARD inline iterator end()noexcept
		{ return iterator(nir<multi, value_type>, _Max()); }

		ZNODISCARD inline const_iterator end()const noexcept
		{ return const_iterator(nir<multi, value_type>, _Max()); }

		ZNODISCARD inline const_iterator cend()const noexcept
		{ return const_iterator(nir<multi, value_type>, _Max()); }

		ZNODISCARD inline reverse_iterator rbegin()const noexcept
		{ return reverse_iterator(_Max()); }

		ZNODISCARD inline const_reverse_iterator crbegin()const noexcept
		{ return const_reverse_iterator(_Max()); }

		ZNODISCARD inline reverse_iterator rend()const noexcept
		{ return reverse_iterator(nir<multi, value_type>, _Min()); }
		
		ZNODISCARD inline const_reverse_iterator crend()const noexcept
		{ return const_reverse_iterator(nir<multi, value_type>, _Min()); }

		inline _rbtree& operator=(_rbtree const& other)
		{
			__construct_range(other.begin(), other.end());
			return *this;
		}

		inline _rbtree& operator=(_rbtree&& other)noexcept
		{
			_m_root = other._m_root;
			_m_cnt  = other._m_cnt;
			other._m_root = nil<multi, value_type>;
			other._m_cnt  = 0;
			return *this;
		}
	
	protected:
		size_type __count(const key& _K)
		{
			_Node_ptr _Iter = __find_node(_K).get_unwrapped();
			if (multi) {
				size_type _Res = 0;
				for (; _Iter; _Iter = _Iter->_m_n) {
					++_Res;
				}
				return _Res;
			}
			if (_Iter == nil<multi, value_type>) {
				return 0;
			}
			return 1;
		}

		inline bool __red_child(_Node_ptr root)
		{ return (root->__l->__col == _Color::red || root->__r->__col == _Color::red); }

		ZNODISCARD inline __tree_node<multi, value_type>* __predecessor(_Node_ptr root)
		{
			_Node_ptr tmp = root->__l;
			for (; tmp->__r != nil<multi, value_type>;) {
				tmp = tmp->__r;
			}
			return tmp;
		}

		ZNODISCARD inline __tree_node<multi, value_type>* __successor(_Node_ptr root)const
		{
			_Node_ptr tmp = root->__r;
			for (; tmp->__l != nil<multi, value_type>;) {
				tmp = tmp->__l;
			}
			return tmp;
		}

		ZNODISCARD inline __tree_node<multi, value_type>* __left_rotate(_Node_ptr root)
		{
			_Node_ptr tmp = root->__r;
			root->__r     = tmp->__l;
			tmp->__l->_m_p = tmp->_m_p;
			tmp->_m_p  = root->_m_p;
			root->_m_p = tmp;
			tmp->__l  = root;
			return tmp;
		}

		ZNODISCARD inline __tree_node<multi, value_type>* __right_rotate(_Node_ptr root)
		{
			_Node_ptr tmp = root->__l;
			root->__l	  = tmp->__r;
			tmp->__r->_m_p = tmp->_m_p;
			tmp->_m_p  = root->_m_p;
			root->_m_p = tmp;
			tmp->__r  = root;
			return tmp;
		}

		ZNODISCARD __tree_node<multi, value_type>* __emplace_balance(_Node_ptr root)
		{
			if (!__red_child(root)) { return root; }
			if (!root->__l->__col && !root->__r->__col) {
				if (!__red_child(root->__l) && !__red_child(root->__r)) {
					return root;
				}
				root->__col = 0;
				root->__l->__col = root->__r->__col = 1;
				return root;
			}
			if (!root->__l->__col && !__red_child(root->__l)) {
				return root;
			}
			if (!root->__r->__col && !__red_child(root->__r)) {
				return root;
			}

			if (!root->__l->__col) {
				if (!root->__l->__r->__col) {
					root->__l = __left_rotate(root->__l);
				}
				root = __right_rotate(root);
			}
			else {
				if (!root->__r->__l->__col) {
					root->__r = __right_rotate(root->__r);
				}
				root = __left_rotate(root);
			}
			root->__col = 0;
			root->__l->__col = 1;
			root->__r->__col = 1;
			return root;
		}

		template<typename Valty, 
			zuck::enable_if_t<zuck::is_same_v<value_type, Valty>, int> = 0>
		ZNODISCARD iterator __find_node(const Valty& val)
		{
			if (_m_root == nir<multi, value_type>) {
				return iterator(nir<multi, value_type>, _Max());
			}
			_Node_ptr ptr = _m_root;
			for (; ptr != nil<multi, value_type>;) {
				if (__equal(val, *(ptr->__d))) {
					return iterator{ ptr, _Max() };
				}
				else if (__cmp(val, *(ptr->__d))) {
					ptr = ptr->__l;
				}
				else {
					ptr = ptr->__r;
				}
			}
			return iterator{ nil<multi, value_type>, _Max() };
		}

		template<typename Valty, 
			zuck::enable_if_t<!zuck::is_same_v<value_type, Valty>, int> = 0>
		ZNODISCARD iterator __find_node(const Valty& val)
		{
			if (_m_root == nir<multi, value_type>) {
				return iterator(nir<multi, value_type>, _Max());
			}
			_Node_ptr ptr = _m_root;
			for (; ptr != nil<multi, value_type> && ptr != null;) {
				if (__equal(val, ptr->__d->first)) {
					return iterator{ ptr, _Max() };
				}
				else if (__cmp(val, ptr->__d->first)) {
					ptr = ptr->__l;
				}
				else {
					ptr = ptr->__r;
				}
			}
			return iterator{ nil<multi, value_type>, _Max() };
		}

	private:
		template<typename Valty, 
			zuck::enable_if_t<zuck::is_same_v<Valty, key>, int> = 0>
		zuck::pair<iterator, bool> __insert_aux(Valty const& val)
		{
			_m_root = __insert(nir<multi, value_type>, _m_root, val);
			_m_root->__col = _Color::black;
			_m_root->_m_p = nir<false, value_type>;
			nir<multi, value_type>->__l =_m_root;

			return __exist ?
				zuck::pair<iterator, bool>(iterator(nir<multi, value_type>, _Max()), !__exist) :
				zuck::pair<iterator, bool>(__find_node(val), !__exist);
		}

		template<typename Valty,
			zuck::enable_if_t<!zuck::is_same_v<Valty, key>, int> = 0>
		zuck::pair<iterator, bool> __insert_aux(Valty const& val)
		{
			_m_root = __insert(nir<multi, value_type>, _m_root, val);
			_m_root->__col = _Color::black;
			_m_root->_m_p = nir<false, value_type>;
			nir<multi, value_type>->__l = _m_root;

			return __exist ?
				zuck::pair<iterator, bool>(iterator(nir<multi, value_type>, _Max()), !__exist) :
				zuck::pair<iterator, bool>(__find_node(val.first), !__exist);
		}

	protected:
		template<typename Valty, 
			zuck::enable_if_t<zuck::is_same_v<key, Valty>, int> = 0>
		__tree_node<multi, Valty>* 
		__insert(_Node_ptr _Parent, _Node_ptr root, Valty const& val)
		{
			__verify_size(_m_cnt);
			if (root == nil<multi, value_type>) {
				root = _Node_Alloc::_Allocate(
					alloc.allocate(1), _Color::red, _Parent, nil<multi, value_type>, nil<multi, value_type>);
				_Alty_tts::construct(root->__d, val);
				__exist = false;
				++_m_cnt;
				return root;
			}
			if (__equal(val, *(root->__d))) {
				if (multi) {
					_Node_ptr _Tmp = _Node_Alloc::_Allocate(alloc.allocate(1), _Color::red, root, _Parent, 
						nil<multi, value_type>, nil<multi, value_type>);
					root = _Tmp;
					_Alty_tts::construct(_Tmp->__d, val);
				}
				else {
					__exist = true;
				}
				return root;
			}
			if (__cmp(val, *(root->__d))) {
				root->__l = __insert(root, root->__l, val);
			}
			else {
				root->__r = __insert(root, root->__r, val);
			}
			return __emplace_balance(root);
		}

		template<typename Valty, 
			zuck::enable_if_t<!zuck::is_same_v<key, Valty>, int> = 0>
		__tree_node<multi, Valty>* 
		__insert(_Node_ptr _Parent, _Node_ptr root, Valty const& val)
		{
			if (root == nil<multi, value_type>) {
				root = _Node_Alloc::_Allocate(
					alloc.allocate(1), _Color::red, _Parent, nil<multi, value_type>, nil<multi, value_type>);
				_Alty_tts::construct(root->__d, val);
				__exist = false;
				++_m_cnt;
				return root;
			}
			if (__equal(val.first, root->__d->first)) {
				if (multi) {

				}
				else {
					__exist = true;
				}
				return root;
			}
			if (__cmp(val.first, root->__d->first)) {
				root->__l = __insert(root, root->__l, val);
			}
			else {
				root->__r = __insert(root, root->__r, val);
			}
			return __emplace_balance(root);
		}

		ZNODISCARD inline __tree_node<multi, value_type>* _Min()const
		{
			_Node_ptr tmp = _m_root;
			for (; tmp->__l != nil<multi, value_type> && tmp != null;) {
				tmp = tmp->__l;
			}
			return tmp;
		}

		ZNODISCARD inline __tree_node<multi, value_type>* _Max()const
		{
			_Node_ptr tmp = _m_root;
			for (; tmp->__r != nil<multi, value_type> && tmp->__r != null;) {
				tmp = tmp->__r;
			}
			return tmp;
		}

		inline void __destroy_tree(_Node_ptr root)
		{
			if (!root || root == nil<multi, value_type>) {
				return;
			}
			__destroy_tree(root->__l);
			__destroy_tree(root->__r);
			alloc.deallocate(root->__d, 1);
			_Node_Alloc::_Deallocate(root);
		}

	protected:
		ZNODISCARD __tree_node<multi, value_type>* __remove_balance(_Node_ptr root)
		{
			if (root->__l->__col != 2 && root->__r->__col != 2) {
				return root;
			}

			if (__red_child(root)) {// has red child
				char flag	= 0;
				root->__col = 0;
				if (!root->__l->__col) {// left child is red
					root = __right_rotate(root);
					flag = 1;
				}
				else {// right child is red
					root = __left_rotate(root);
					flag = 2;
				}
				root->__col = 1;
				if (flag == 1) { root->__r = __remove_balance(root->__r); }
				else { root->__l = __remove_balance(root->__l); }
				return root;
			}

			if ((root->__l->__col == 2 && !__red_child(root->__r)) ||
				(root->__r->__col == 2 && !__red_child(root->__l)))
			{
				root->__l->__col = 1;
				root->__r->__col = 1;
				root->__col += 1;
				return root;
			}

			if (root->__l->__col == 2) {
				root->__l->__col = 1;

				if (root->__r->__r->__col != 0) {
					root->__r->__col = 0;
					root->__r = __right_rotate(root->__r);
					root->__r->__col = 1;
				}

				root = __left_rotate(root);
				root->__col = root->__l->__col;
			}
			else {
				root->__r->__col = 1;

				if (root->__l->__l->__col != 0) {
					root->__l->__col = 0;
					root->__l = __left_rotate(root->__l);
					root->__l->__col = 1;
				}
				root = __right_rotate(root);
				root->__col = root->__r->__col;
			}
			root->__l->__col = root->__r->__col = 1;
			return root;
		}

	private:
		template<typename PointerType>
		inline void __construct_range(PointerType Begin, PointerType End)
		{
			auto const _Dis = zuck::distance(Begin, End);
			__verify_size(_Dis);
			for (; Begin != End; ++Begin) {
				__insert(nir<multi, value_type>, _m_root, *Begin);
			}
		}

		void __copy_aux(const _Self& other)
		{
			if (_m_cnt) {
				__destroy_tree();
			}

			auto Begin = other.begin();
			auto const End = other.end();

			for (; Begin != End; ++Begin) {
				__insert(nir<multi, value_type>, _m_root, *Begin);
			}
		}

		inline void __verify_size(size_type const _Newsize)
		{
			auto const _Max = max_size();
			if (_Newsize >= _Max) {
				debug_log::derror(
					zuck::SEG_LengthTooLong, 
					"map / set's length too long !");
			}
		}
	};
}

